#pragma once

#include "algo_base.hpp"
#include "algo_meta_func.hpp"
#include "type_traits.hpp"
#include "temporary_buffer.hpp"

namespace zuck
{
    template<
        typename DataType1, typename DataType2, 
        zuck::enable_if_t<zuck::is_integral_v<DataType1> && 
        zuck::is_integral_v<DataType2>, int> = 0>
    [[nodiscard]] inline zuck::conditional_t<sizeof(DataType2) < sizeof(DataType1), DataType1, DataType2>
        sum(DataType1 data1, DataType2 data2)
    {
        return data1 + data2;
    }

    template<typename DataType1, typename DataType2>
    [[nodiscard]] inline zuck::conditional_t<zuck::is_floating_v<DataType1>, DataType1, DataType2>
    sum(DataType1 data1, DataType2 data2)
    {
        return data1 + data2;
    }

    // InputIterator
    template<typename InputIterator,
        typename Valty = typename InputIterator::iterator_category,
        zuck::enable_if_t<zuck::is_input_iterator_v<InputIterator>, int> = 0>
    [[nodiscard]] Valty sum(InputIterator Begin, InputIterator End)
    {
        Valty res = Valty{};
        for (; Begin != End; ++Begin) {
            res += *Begin;
        }
        return res;
    }

    template<typename Integer1, typename Integer2, 
        zuck::enable_if_t<zuck::is_integral_v<Integer1> && zuck::is_integral_v<Integer2>, int> = 0>
    [[nodiscard]] inline zuck::conditional_t<sizeof(Integer1) < sizeof(Integer2), Integer2, Integer1>
    avg(Integer1 _LNum, Integer2 _RNum)
    {
        return (_LNum & _RNum) + ((_LNum ^ _RNum) >> 1);
    }


    template<typename Float1, typename Float2, 
        zuck::enable_if_t<zuck::is_floating_v<Float1> || zuck::is_floating_v<Float2>, int> = 0>
    [[nodiscard]] inline zuck::conditional_t<zuck::is_floating_v<Float2>, Float2, Float1>
    avg(Float1 lNum, Float2 rNum)
    {
        return (lNum + rNum) / 2;
    }

    template<typename InputIterator, 
        typename Valty  = zuck::iter_traits_t<InputIterator>, 
        typename Diff_t = zuck::iter_traits_t<InputIterator>, 
        zuck::enable_if_t<zuck::is_input_iterator_v<InputIterator>, int> = 0>
    [[nodiscard]] inline Valty avg (InputIterator Begin, InputIterator End)
    {
        Valty res   = Valty{};
        Diff_t _Dis = 0;
        for (; Begin != End; ++Begin) {
            res += *Begin;
            ++_Dis;
        }
        return res / _Dis;
    }

    
// ForwardIterator
    template<
        typename ForwardIterator,
        typename _Val_t = zuck::iter_traits_t<ForwardIterator>,
        typename _Cmp   = zuck::less<_Val_t>
    >// O(log n)
    [[nodiscard]] ForwardIterator lower_bound 
    (ForwardIterator _Begin, ForwardIterator _End, const _Val_t& val, const _Cmp& _pred = zuck::less<_Val_t>{})
    {
        using RmRefType = remove_ref_t<ForwardIterator>;
        using DiffType  = iter_diff_t<ForwardIterator>;

        RmRefType first = _Begin;
        DiffType  _Dis  = zuck::distance(_Begin, _End);

        for (; 0 < _Dis;) {
            DiffType  _Dis2 = (_Dis >> 1);
            RmRefType _Mid  = zuck::advance(first, _Dis2);
            if (_pred(*_Mid, val)) {
                first = ++_Mid;
                _Dis -= (_Dis2 + 1);
            } 
            else {
                _Dis = _Dis2;
            }
        }
        return first;
    }


    template<
        typename ForwardIterator, 
        typename _Val_t  = zuck::iter_traits_t<ForwardIterator>, 
        typename _Diff_t = zuck::iter_diff_t<ForwardIterator>, 
        typename _Cmp    = zuck::less<_Val_t>
    >// O(log n)
    [[nodiscard]] ForwardIterator
    upper_bound(ForwardIterator _Begin, ForwardIterator _End, const _Val_t& val, 
        const _Cmp& _pred = zuck::less<_Val_t>{})
    {
        using RmRefType = remove_ref_t<ForwardIterator>;
        using DiffType  = iter_diff_t<ForwardIterator>;

        RmRefType first = _Begin;
        DiffType  _Dis  = zuck::distance(_Begin, _End);
        for (; 0 < _Dis;) {
            DiffType  _Dis2 = (_Dis >> 1);
            RmRefType _Mid  = zuck::advance(first, _Dis2);
            if (_pred(val, *_Mid)) {
                first = ++_Mid;
                _Dis -= _Dis2 + 1;
            }
            else {
                _Dis = _Dis2;
            }
        }
        return first;
    }

    
    template<
        typename ForwardIterator, 
        typename _Val_t = zuck::iter_traits_t<ForwardIterator>
    >
    [[nodiscard]] size_t count(ForwardIterator Begin, ForwardIterator End, const _Val_t& val)
    {
        // O(n)
        size_t cnt{};
        for (; Begin != End; ++Begin) {
            if (*Begin == val) {
                ++cnt;
            }
        }
        return cnt;
    }


    template<typename ForwardIterator, typename Func>
    [[nodiscard]] size_t 
    count_if(ForwardIterator Begin, ForwardIterator End, Func _Pr)
    {// O(n)
        size_t cnt{ 0 };
        for (; Begin != End; ++Begin) {
            if (_Pr(*Begin)) {
                ++cnt;
            }
        }
        return cnt;
    }

    template<typename BidirectIter>
    void reverse(BidirectIter first, BidirectIter last)
    {
        for (; first != last;) {
            zuck::iter_swap(first++, --last);
        }
    }

    template<typename BidirectIter, typename _Val_t = zuck::iter_traits_t<BidirectIter>,
        typename _Cmp = zuck::less<_Val_t>
    >
    [[nodiscard]] bool next_permutation(BidirectIter first, BidirectIter last, 
        _Cmp const& _pred = zuck::less<_Val_t>{})
    {
        if (first == last) {
            return false;
        }
        BidirectIter i = first;
        ++i;
        if (i == last) {
            return false;
        }
        i = last;
        --i;

        for (;;) {
            BidirectIter ii = i;
            --i;
            if (_pred(*i, *ii)) {
                BidirectIter j = last;
                for (; _pred(*i, *--j);) {}
                zuck::iter_swap(i, j);
                zuck::reverse(ii, last);
            }
            if (i == first) {
                zuck::reverse(first, last);
                return false;
            }
        }
        return false;
    }


    template<typename BidirectIter, typename _Val_t = zuck::iter_traits_t<BidirectIter>,
        typename _Cmp = zuck::less<_Val_t>
    >
    [[nodiscard]] bool prev_permutation(BidirectIter first, BidirectIter last, 
        _Cmp const& _pred = zuck::less<_Val_t>{})
    {
        if (first == last) {
            return false;
        }
        BidirectIter i = first;
        ++i;
        if (i == last) {
            return false;
        }
        i = last;
        --i;

        for (;;) {
            BidirectIter ii = i;
            --i;
            if (_pred(*ii, *i)) {
                BidirectIter j = last;
                for (; !_pred(*--j, *i);) {}
                zuck::iter_swap(i, j);
                zuck::reverse(ii, last);
                return true;
            }
            if (i == first) {
                zuck::reverse(first, last);
                return false;
            }
        }
        return false;
    }


    template<
        typename RandomIter,
        typename _Val_t = zuck::iter_traits_t<RandomIter>,
        typename _Cmp   = zuck::less<_Val_t>
    >
    void push_heap(RandomIter first, RandomIter last, _Cmp const& _pred = zuck::less<_Val_t>{})
    {
        zuck::__push_heap(first, ((last - first) - 1), 0, *(last - 1), _pred);
    }

    template<
        typename RandomIter,
        typename _Val_t = zuck::iter_traits_t<RandomIter>,
        typename _Cmp   = zuck::less<_Val_t>
    >
    void pop_heap(RandomIter first, RandomIter last, _Cmp _pred = zuck::less<_Val_t>{})
    {
        zuck::__pop_heap(first, last - 1, last - 1, *(last - 1), _pred);
    }

    template<
        typename RandomIter,
        typename _Diff_t = zuck::iter_diff_t<RandomIter>,
        typename _Val_t  = zuck::iter_traits_t<RandomIter>,
        typename _Cmp    = zuck::less<_Val_t>
    >
    void make_heap(RandomIter first, RandomIter last, _Cmp const& _pred = zuck::less<_Val_t>{})
    {// O(n)
        if ((last - first) < 2) {
            return;
        }

        _Diff_t _len{ last - first };
        _Diff_t _par{ (_len - 2) >> 1};// array tail

        for (;;) {
            zuck::__adjust_heap(first, _par, _len, *(first + _par), _pred);
            if (_par == 0) { return; }
            --_par;
        }
    }


    template<typename RandomIter, 
            typename _Val_t = zuck::iter_traits_t<RandomIter>, 
            typename _Cmp   = zuck::less<_Val_t>
    >// O(n * logn)
    void sort_heap
    (RandomIter first, RandomIter last, _Cmp const& _pred = zuck::less<_Val_t>{})
    {
        static_assert(!zuck::is_pointer_v<RandomIter> ||
            !zuck::is_random_access_iterator_v<typename RandomIter::iterator_category>,
            "invalid parameter first and last");

        for (; 1 < last - first;) {
            zuck::pop_heap(first, last--, _pred);
        }
    }


    template<typename RandomIter,
            typename _Val_t = zuck::iter_traits_t<RandomIter>,
            typename _Cmp   = zuck::less<_Val_t>
    >
    void partitial_sort
    (RandomIter first, RandomIter middle, RandomIter last, const _Cmp& _pred = zuck::less<_Val_t>{})
    {
        static_assert(!zuck::is_random_access_iterator_v<RandomIter>,
            "invalid parameter first and last");

        zuck::make_heap(first, middle);
        for (RandomIter i = middle; i != last; ++i) {
            if (_pred(*i, *first)) {
                zuck::__pop_heap(first, middle, i, *i, _pred);
            }
        }
        zuck::sort_heap(first, middle);
    }


    zuck::ptrdiff_t constexpr therholds = 0x020;
    template<
        typename RandomIter,
        typename _Val_t  = zuck::iter_traits_t<RandomIter>,
        typename _Diff_t = zuck::iter_diff_t<RandomIter>,
        typename _Cmp    = zuck::less<_Val_t>
    >
    void __sort_loop
    (RandomIter first, RandomIter last, iter_diff_t<RandomIter> depth, _Cmp _pred = zuck::less<_Val_t>{})
    {
        for (; therholds < last - first;) {
            if (!depth) {
                zuck::partitial_sort(first, last, last, _pred);
                return;
            }
            --depth;
            using _Unwrapp_t = remove_ref_t<RandomIter>;
            _Unwrapp_t low  = first;
            _Unwrapp_t high = last - 1;
            _Val_t     div  = *low;
            do {
                for (; _pred(div, *high);) {
                    --high;
                }
                for (; _pred(*low, div);) {
                    ++low;
                }
                if (low <= high) {
                    zuck::iter_swap(low, high);
                    ++low; --high;
                }
            } while (low <= high);

            zuck::__sort_loop(low, last, depth, _pred);
            last = high + 1;
        }
    }


    template<typename RandomIter, typename Valty = zuck::iter_traits_t<RandomIter>, typename _Cmp = zuck::less<Valty>>
    void sort(RandomIter first, RandomIter last, _Cmp pred = zuck::less<Valty>{})
    {
        static_assert(!zuck::is_pointer_v<RandomIter> || 
            !zuck::is_random_access_iterator_v<RandomIter>, 
            "invalid parameter first and last");

        if (first != last) {
            zuck::__sort_loop(first, last, (zuck::__lg(last - first) >> 1), pred);
            zuck::insertion_sort_uncheck(first, last, pred);
        }
    }

    template<
        typename BidirectIter,
        typename _Val_t = zuck::iter_traits_t<BidirectIter>,
        typename _Cmp   = zuck::less<_Val_t>
    >
    void stable_sort(BidirectIter first, BidirectIter last, _Cmp const& _pred = less<_Val_t>{})
    {
        if (last - first <= therholds) {
            zuck::insertion_sort_uncheck(first, last, _pred);
            return;
        }

        zuck::__temporary_buffer<BidirectIter>__temp_buff(first, last);
        // TODO...
    }


// sequence search first elem if equal to val
    template<
        typename ForwardIterator,
        typename _Val_t = zuck::iter_traits_t<ForwardIterator>
    >
    ForwardIterator find(ForwardIterator _Begin, ForwardIterator _End, _Val_t const& val)
    {
        for (; _Begin != _End; ++_Begin) {
            if (*_Begin == val) {
                return _Begin;
            }
        }
        return ForwardIterator{};
    }


// sequence search first elem if _pred(*iter)
    template<
        typename ForwardIterator,
        typename Func,
        typename _Val_t = zuck::iter_traits_t<ForwardIterator>
    >
    ForwardIterator find_if(ForwardIterator bgn, ForwardIterator end, Func _pred)
    {
        for (; bgn != end; ++bgn) {
            if (_pred(*bgn)) {
                return bgn;
            }
        }
        return ForwardIterator{};
    }


    template<typename ForwardIterator, typename Pred>
    void for_each
    (ForwardIterator first, ForwardIterator last, Pred _Pr)
    {
        for (; first != last; ++first) {
            _Pr(*first);
        }
    }


    template<typename ForwardIterator,
            typename Valty = zuck::iter_traits_t<ForwardIterator>,
            typename Predi = zuck::less<Valty>
    >
    [[nodiscard]] bool binary_search
    (ForwardIterator _Begin, ForwardIterator _End, Valty _Val, Predi _Pr = zuck::less<Valty>{})
    {
        using _UnWarpped_t = remove_ref_t<ForwardIterator>;

        _UnWarpped_t first = _Begin;
        _UnWarpped_t last  = _End;
        first              = zuck::lower_bound(_Begin, _End, _Val, _Pr);

        return static_cast<bool>(first != last && !_Pr(_Val, *first));
    }


    template<typename RandomIter,
            typename _Diff_t = zuck::iter_diff_t<RandomIter>,
            typename _Val_t  = zuck::iter_traits_t<RandomIter>,
            typename _Cmp    = zuck::less<_Val_t>
    >
    [[nodiscard]] bool is_heap
    (RandomIter first, RandomIter last, const _Cmp& _pred = zuck::less<_Val_t>{})
    {
        _Diff_t dis = last - first;
        _Diff_t par = _Diff_t{};

        for (_Diff_t child = 1; child < dis; ++child) {
            if (_pred(*(first + par), *(first + child))) {
                return false;
            }
            if (!(child & 1)) {
                ++par;
            }
        }
        return true;
    }


    template<typename ForwardIterator, 
        typename Valty = zuck::iter_traits_t<ForwardIterator>, 
        typename Predi = zuck::less<Valty>
    >
    [[nodiscard]] ForwardIterator min_elem
    (ForwardIterator Begin, ForwardIterator End, Predi pred = zuck::less<Valty>{})
    {
        ForwardIterator _Res = Begin;
        ++Begin;
        for (; Begin != End; ++Begin) {
            if (pred(*Begin, *_Res)) {
                _Res = Begin;
            }
        }
        return _Res;
    }


    template<typename FwdIterator,
        typename Valty = zuck::iter_traits_t<FwdIterator>,
        typename Predi = zuck::greater<Valty>
    >
    [[nodiscard]] FwdIterator max_element(FwdIterator Begin, FwdIterator End, Predi pred = zuck::greater<Valty>{})
    {
        FwdIterator _Res = Begin;
        ++Begin;
        for (; Begin != End; ++Begin) {
            if (pred(*Begin, *_Res)) {
                _Res = Begin;
            }
        }
        return _Res;
    }

    [[nodiscard]] float rsqrt(const float& number)
    {
        long i = 0;
        float x2 = 0.f, y = 0.f;
        const float threehalfs = 1.5f;
        x2 = number * 0.5f;
        y  = number;
        i  = *reinterpret_cast<long*>(&y);		// evil floating point bit hack
        i  = 0x5f3759df - (i >> 1);			    // ...... ?
        y  = *reinterpret_cast<float*>(&i);
        y  = y * (threehalfs - (x2 * y * y));	// iteration

        return y;
    }

namespace __detail {
    class _Pow_functor {
    public:
        template<typename B, typename Uint, enable_if_t<is_unsigned_v<Uint>, int> = 0>
        [[nodiscard]] B operator()(const B btom, Uint cnt)const
        {
            B ret = B(1);
            for (; cnt; --cnt) {
                ret *= btom;
            }
            return ret;
        }
    };

    class _FastPow_functor {
    public:
        template<typename B, typename Uint, enable_if_t<is_unsigned_v<Uint>, int> = 0>
        [[nodiscard]] B operator()(const B btom, Uint cnt)const
        {
            B tmp = btom, ret = B(1);

            for (; cnt;) {
                if (cnt & 1) {
                    ret *= tmp;
                }
                cnt >>= 1;
                tmp *= tmp;
            }
            return ret;
        }
    };
}
    constexpr __detail::_FastPow_functor fast_pow = {};
    constexpr __detail::_Pow_functor pow = {};
}

